package top150

import (
	"bytes"
	"math"
	"sort"
	"strconv"
	"strings"
)

func reverseWords(s string) string {
	var str = strings.Trim(s, " ")
	var strs = strings.Fields(str)
	var left = 0
	var right = len(strs) - 1
	for left < right {

		strs[left], strs[right] = strs[right], strs[left]
		left++
		right--

	}

	return strings.Join(strs, " ")
}

func reverseWordsII(s string) string {
	var strs []string
	var idx = 0
	for idx < len(s) {
		for idx < len(s) && s[idx] == ' ' {
			idx++
		}
		var cur []byte
		for idx < len(s) && s[idx] != ' ' {
			cur = append(cur, s[idx])
			idx++
		}
		if len(cur) > 0 {
			strs = append(strs, string(cur))
		}
	}
	var left = 0
	var right = len(strs) - 1
	for left < right {
		strs[left], strs[right] = strs[right], strs[left]
		left++
		right--

	}

	return strings.Join(strs, " ")
}

func convert(s string, numRows int) string {
	var res = make([][]byte, numRows)
	var addNum = -1
	var curRow = -1
	for i := 0; i < len(s); i++ {
		if i%numRows == 0 {
			addNum = -addNum
		}
		curRow += addNum
		res[curRow] = append(res[curRow], s[i])
	}
	var resStr string
	for i := 0; i < numRows; i++ {
		resStr += string(res[i])
	}
	return resStr
}

func isPalindrome(s string) bool {
	var str []byte
	for i := 0; i < len(s); i++ {
		if isLetter(s[i]) {
			str = append(str, s[i])
		}
	}
	var left = 0
	var right = len(str) - 1
	str = bytes.ToLower(str)
	for left < right {
		if str[left] != str[right] {
			return false
		}
		left++
		right--
	}
	return true
}

func isLetter(a byte) bool {
	return (a >= 'a' && a <= 'z') || (a >= 'A' && a <= 'Z') || (a >= '0' && a <= '9')
}

func lengthOfLongestSubstring(s string) int {
	// 滑动窗口
	var windowMap = make(map[byte]int)
	var max = 0
	var left = 0
	for i := 0; i < len(s); i++ {
		if idx, ok := windowMap[s[i]]; !ok {
			windowMap[s[i]] = i
			if len(windowMap) > max {
				max = len(windowMap)
			}
		} else {
			for j := left; j <= idx; j++ {
				delete(windowMap, s[j])
			}
			windowMap[s[i]] = i
			left = idx + 1
		}
	}
	return max
}

func findSubstring(s string, words []string) []int {
	// 排除特殊情况
	if len(words) == 0 {
		return nil
	}
	wordLen := len(words[0])
	combLen := len(words) * wordLen
	if len(s) < combLen {
		return nil
	}

	var indices []int
	m := make(map[string]int)
	for _, word := range words {
		m[word]++
	}
	// 分wordLen批次比较子串
	for i := 0; i < wordLen; i++ {
		counter := make(map[string]int)
		left, right := i, i
		num := 0
		for right+wordLen <= len(s) {
			word := s[right : right+wordLen]
			right += wordLen
			// 若word在words中不存在
			if m[word] == 0 {
				left = right
				num = 0
				for word := range counter {
					counter[word] = 0
				}
				continue
			}

			counter[word]++
			num++
			// 若word重复了
			for counter[word] > m[word] {
				counter[s[left:left+wordLen]]--
				left += wordLen
				num--

				continue
			}
			// 若子串中的单词与words中的单词完全匹配
			if num == len(words) {
				indices = append(indices, left)
				counter[s[left:left+wordLen]]--
				num--
				left += wordLen
			}
		}
	}

	return indices
}

func gameOfLife(board [][]int) {
	// 由 活 变死 ，1 -》 -1
	// 由 死 变活 ，0 -》 2
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if board[i][j] == 1 {
				if !aliveCntBiggerThan(board, i, j, 2, 8) {
					board[i][j] = -1
				}
			} else if aliveCntBiggerThan(board, i, j, 3, 3) {
				board[i][j] = 2
			}
		}
	}

	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if board[i][j] == -1 {
				board[i][j] = 0
			} else if board[i][j] == 2 {
				board[i][j] = 1
			}
		}
	}

}

func aliveCntBiggerThan(board [][]int, i, j, minCnt, maxCnt int) bool {
	var aliveCnt = 0
	// 上
	if i-1 >= 0 {
		// 上
		if board[i-1][j] == 1 || board[i-1][j] == -1 {
			aliveCnt++
		}
		// 左上
		if j-1 >= 0 && (board[i-1][j-1] == 1 || board[i-1][j-1] == -1) {
			aliveCnt++
		}
		// 右上
		if j+1 < len(board[i]) && (board[i-1][j+1] == 1 || board[i-1][j+1] == -1) {
			aliveCnt++
		}
	}
	// 下
	if i+1 < len(board) {
		// 下
		if board[i+1][j] == 1 {
			aliveCnt++
		}
		// 左下
		if j-1 >= 0 && board[i+1][j-1] == 1 {
			aliveCnt++
		}
		// 右下
		if j+1 < len(board[i]) && board[i+1][j+1] == 1 {
			aliveCnt++
		}
	}

	// 左
	if j-1 >= 0 && (board[i][j-1] == 1 || board[i][j-1] == -1) {
		aliveCnt++
	}
	// 右
	if j+1 < len(board[i]) && board[i][j+1] == 1 {
		aliveCnt++
	}
	return aliveCnt >= minCnt && aliveCnt <= maxCnt
}
func groupAnagrams(strs []string) [][]string {
	var strMap = make(map[[26]int][]string)

	for i := 0; i < len(strs); i++ {
		var chArr = new([26]int)
		for j := 0; j < len(strs[i]); j++ {
			chArr[strs[i][j]-'a']++
		}
		if val, ok := strMap[*chArr]; ok {
			val = append(val, strs[i])
			strMap[*chArr] = val
		} else {
			strMap[*chArr] = []string{strs[i]}
		}
	}
	var res [][]string
	for _, val := range strMap {
		res = append(res, val)
	}
	return res
}
func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	var res [][]int
	res = append(res, intervals[0])
	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] > res[len(res)-1][1] {
			res = append(res, intervals[i])
		} else if intervals[i][1] > res[len(res)-1][1] {
			res[len(res)-1][1] = intervals[i][1]
		}
	}
	return res
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func insert(intervals [][]int, newInterval []int) [][]int {
	res := make([][]int, 0)
	l := len(intervals)
	i := 0
	for i < l && intervals[i][1] < newInterval[0] {
		res = append(res, intervals[i])
		i++
	}
	for i < l && intervals[i][0] <= newInterval[1] {
		newInterval[0] = min(newInterval[0], intervals[i][0])
		newInterval[1] = max(newInterval[1], intervals[i][1])
		i++
	}
	res = append(res, newInterval)
	for i < l {
		res = append(res, intervals[i])
		i++
	}
	return res
}

func evalRPN(tokens []string) int {
	var nums []int
	for i := 0; i < len(tokens); i++ {
		var nextVal int

		if tokens[i] == "+" {
			var leftVal = nums[len(nums)-2]
			var rightVal = nums[len(nums)-1]
			nextVal = leftVal + rightVal
			nums[len(nums)-2] = nextVal
			nums = nums[0 : len(nums)-1]
		} else if tokens[i] == "-" {
			var leftVal = nums[len(nums)-2]
			var rightVal = nums[len(nums)-1]
			nextVal = leftVal - rightVal
			nums[len(nums)-2] = nextVal
			nums = nums[0 : len(nums)-1]
		} else if tokens[i] == "*" {
			var leftVal = nums[len(nums)-2]
			var rightVal = nums[len(nums)-1]
			nextVal = leftVal * rightVal
			nums[len(nums)-2] = nextVal
			nums = nums[0 : len(nums)-1]
		} else if tokens[i] == "/" {
			var leftVal = nums[len(nums)-2]
			var rightVal = nums[len(nums)-1]
			nextVal = leftVal / rightVal
			nums[len(nums)-2] = nextVal
			nums = nums[0 : len(nums)-1]
		} else {
			val, _ := strconv.ParseInt(tokens[i], 10, 64)
			nums = append(nums, int(val))
		}

	}

	return nums[0]
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func averageOfLevels(root *TreeNode) []float64 {
	var res []float64
	var queue = []*TreeNode{
		root,
	}
	for len(queue) > 0 {
		var size = len(queue)
		var sum = 0
		for i := 0; i < size; i++ {
			sum += queue[i].Val
			if queue[i].Left != nil {
				queue = append(queue, queue[i].Left)
			}
			if queue[i].Right != nil {
				queue = append(queue, queue[i].Right)
			}
		}
		queue = queue[size:]
		res = append(res, float64(sum)/float64(size))
	}
	return res
}

/**
 * @description: 207.课程表
 * @keyword:
 * @author: kami
 * @date 2024/2/23 20:03
 */
func canFinish(numCourses int, prerequisites [][]int) bool {
	var size = len(prerequisites)
	if size == 0 {
		return true
	}
	// {1, 4}, {2, 4}, {3, 1}, {3, 2},
	var pointer = make([]int, numCourses)
	for i := 0; i < size; i++ {
		pointer[prerequisites[i][0]]++
	}
	var removed = make([]bool, size)
	var remove int
	for remove < size {
		var curRemove int
		for i := 0; i < size; i++ {
			if removed[i] {
				continue
			}
			if pointer[prerequisites[i][1]] == 0 {
				pointer[prerequisites[i][0]]--
				removed[i] = true
				curRemove++
			}
		}
		if curRemove == 0 {
			return false
		}
		remove += curRemove
	}
	return true
}

func findOrder(numCourses int, prerequisites [][]int) []int {
	var size = len(prerequisites)
	if size == 0 {
		var res []int
		for i := 0; i < numCourses; i++ {
			res = append(res, i)
		}
		return res
	}
	var pointer = make([]int, numCourses)
	for i := 0; i < size; i++ {
		pointer[prerequisites[i][0]]++
	}
	var removed = make([]bool, size)
	var remove int
	var res []int
	var handleMap = make(map[int]bool)
	for remove < size {
		var curRemove int
		for i := 0; i < size; i++ {
			if removed[i] {
				continue
			}
			if pointer[prerequisites[i][1]] == 0 {
				pointer[prerequisites[i][0]]--
				removed[i] = true
				if !handleMap[prerequisites[i][1]] {
					res = append(res, prerequisites[i][1])
					handleMap[prerequisites[i][1]] = true
				}
				curRemove++
			}
		}
		if curRemove == 0 {
			return []int{}
		}
		remove += curRemove
	}

	for i := 0; i < numCourses; i++ {
		if !handleMap[i] {
			res = append(res, i)
		}
	}
	return res
}
func letterCombinations(digits string) []string {
	var res []string
	if len(digits) == 0 {
		return res
	}
	var trackBack func(digits string, idx int, curRes string)
	trackBack = func(digits string, idx int, curRes string) {
		if len(curRes) == len(digits) {
			res = append(res, curRes)
			return
		}
		var chars = mapToString(digits[idx])

		for i := 0; i < len(chars); i++ {
			trackBack(digits, idx+1, curRes+string(chars[i]))
		}

	}
	trackBack(digits, 0, "")
	return res
}
func mapToString(num byte) string {
	switch num {
	case '2':
		return "abc"
	case '3':
		return "def"
	case '4':
		return "ghi"
	case '5':
		return "jkl"
	case '6':
		return "mno"
	case '7':
		return "pqrs"
	case '8':
		return "tuv"
	default:
		return "wxyz"
	}
}
func combinationSum(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	var res [][]int
	var trackBack func(nums, curRes []int, curSum, target, idx int)
	trackBack = func(nums, curRes []int, curSum, target, idx int) {
		if curSum > target {
			return
		}
		if curSum == target {
			var temp = make([]int, len(curRes))
			copy(temp, curRes)
			res = append(res, temp)
			return
		}
		for i := idx; i < len(nums); i++ {
			curSum += nums[i]
			if curSum > target {
				break
			}
			curRes = append(curRes, nums[i])
			trackBack(nums, curRes, curSum, target, i)
			curSum -= nums[i]
			curRes = curRes[:len(curRes)-1]
		}
	}
	trackBack(candidates, []int{}, 0, target, 0)
	return res
}

/**
 * @description: 4.寻找两个正序数组的中位数
 * @keyword:
 * @author: kami
 * @date 2024/2/26 15:28
 */
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	if len(nums1) > len(nums2) {
		return findMedianSortedArrays(nums2, nums1)
	}
	var m = len(nums1)
	var n = len(nums2)
	var totalLeft = (m + n + 1) / 2
	var left = 0
	var right = m
	// 交叉小于等于
	for left < right {
		var i = left + (right-left+1)/2
		var j = totalLeft - i
		if nums1[i-1] > nums2[j] {
			// 下一轮搜索的区间 left，i-1
			right = i - 1
		} else {
			left = i
		}
	}
	var i = left
	var j = totalLeft - i
	var nums1LeftMax = math.MinInt
	if i > 0 {
		nums1LeftMax = nums1[i-1]
	}
	var nums1RightMin = math.MaxInt
	if i < m {
		nums1RightMin = nums1[i]
	}
	var nums2LeftMax = math.MinInt
	if j > 0 {
		nums2LeftMax = nums2[j-1]
	}
	var nums2RightMin = math.MaxInt
	if j < n {
		nums2RightMin = nums2[j]
	}
	if (m+n)%2 == 1 {
		return float64(getMax(nums1LeftMax, nums2LeftMax))
	} else {
		return float64(getMax(nums1LeftMax, nums2LeftMax)+getMin(nums1RightMin, nums2RightMin)) / 2
	}

}
func getMin(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func getMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}
